package com.classicInterview;

/**
 * 贪心算法
 * 求解至少经过多少轮，可以使数组每个位置都相等，每个位置每次只能向右或向左扔出一件衣服
 *
 * @Author: huangzhigao
 * @Date: 2022/2/12 12:27
 */
public class PackingMachine {

    public int minOpts(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int size = arr.length;
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }

        //当总和与总大小取余不等于0，则一定不平
        if (sum % size != 0) {
            return -1;
        }
        //每个位置的数
        int avg = sum / size;

        int leftSum = 0;
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            //左边需要扔的衣服
            int leftSumRes = leftSum - i * avg;
            int rightSumRes = sum - leftSum - arr[i] - (size - i - 1) * avg;
            if (leftSumRes < 0 && rightSumRes < 0) {
                //需要i位置向左右两便仍衣服，则至少需要leftSumRes+rightSumRes
                ans = Math.max(ans, Math.abs(leftSumRes) + Math.abs(rightSumRes));
            } else {
                //则需要左右两边剩余最大的次数
                ans = Math.max(ans, Math.max(Math.abs(leftSumRes), Math.abs(rightSumRes)));
            }
            leftSum += arr[i];
        }
        return ans;
    }
}
